1. Field of the Invention
The present invention is directed to computer systems; and more particularly, it is directed to tessellation of geometric objects using computer systems.
2. Description of the Related Art
As the power and complexity of personal computer systems increase, graphics operations are increasingly being performed using dedicated graphics rendering devices referred to as graphics processing units (GPUs). As used herein, the terms “graphics processing unit” and “graphics processor” are used interchangeably. GPUs are often used in removable graphics cards that are coupled to a motherboard via a standardized bus (e.g., AGP, PCI, or PCI Express). GPUs may also be used in game consoles and in integrated graphics solutions (e.g., for use in some portable computers and lower-cost desktop computers). Although GPUs vary in their capabilities, they may typically be used to perform such tasks as rendering of two-dimensional (2D) graphical data, rendering of three-dimensional (3D) graphical data, accelerated rendering of graphical user interface (GUI) display elements, and digital video playback. A GPU may implement one or more application programmer interfaces (APIs) that permit programmers to invoke the functionality of the GPU.
To reduce demands on central processing units (CPUs) of computer systems, GPUs may be tasked with performing operations that would otherwise contribute to the CPU load. Accordingly, modern GPUs are typically implemented with specialized features for efficient performance of common graphics operations. For example, a GPU often includes a plurality of execution channels that can be used simultaneously for highly parallel processing. A GPU may include various built-in and configurable structures for rendering digital images to an imaging device.
Digital images may include raster graphics, vector graphics, or a combination thereof. Raster graphics data (also referred to herein as bitmaps) may be stored and manipulated as a grid of individual picture elements called pixels. A bitmap may be characterized by its width and height in pixels and also by the number of bits per pixel. Commonly, a color bitmap defined in the RGB (red, green blue) color space may comprise between one and eight bits per pixel for each of the red, green, and blue channels. An alpha channel may be used to store additional data such as per-pixel transparency values.
Vector graphics data may be stored and manipulated as one or more geometric objects built with geometric primitives. The geometric primitives (e.g., points, lines, polygons, Bézier curves, and text characters) may be based upon mathematical equations to represent parts of digital images. The geometric objects may typically be located in two-dimensional or three-dimensional space. Suitable image editors, such as Adobe Illustrator® (available from Adobe Systems, Inc.), may be used to perform operations on these objects. Typical operations include rotation, translation, stretching, skewing, changing depth order, and combining objects with other objects. While raster graphics may often lose apparent quality when scaled to a higher resolution, vector graphics may scale to the resolution of the device on which they are ultimately rendered.
To render vector graphics on raster-based imaging devices (e.g., most display devices and printers), the geometric objects are typically converted to raster graphics data in a process called rasterization. Prior to final rasterization, surfaces defined by the geometric objects may be covered with polygons (e.g., triangles or quadrilaterals) in a process called tessellation or triangulation. The polygons may also be referred to as tessellae, and the arrangement of polygons may be referred to as a triangulation or a mesh. Each polygon is defined by at least three vertices, and each vertex may be characterized by color and alpha values. Because tessellation of a shaded surface may produce many polygons, a surface may be rendered with fine variations in the color and alpha values.
In tessellating a two-dimensional geometric object that includes a curved path, the curve may be approximated by a series of line segments. The polygon may then be tessellated using conventional polygon triangulation techniques such as Siedel, Watson, Delaunay, etc., to produce a set of triangles. The approximation of the curve may be referred to as “flattening.” The resulting polygon typically has a large number of vertices in the area approximating the curve. However, the number of line segments and the corresponding number of vertices used in approximating the curve may be dependent upon the resolution of the target output device (e.g., a display device or printer).
One prior approach to tessellation uses “cancelling triangles” to produce a multi-cover triangulation describing the interior of a two-dimensional geometric object. Using this approach, a point may be chosen (e.g., the center of the object bounds), and triangles connecting every edge to the chosen point may be produced. However, this approach may produce undesirably “spiky” triangles on polygons having a high vertex count such as polygons having segments that approximate a curve. FIG. 1A illustrates an example triangulation 50 produced using this approach.
As the resolution of the polygonal boundary increases, the triangulation may become even “spikier” using this prior approach. Furthermore, the increased “spikiness” of a triangulation may increase the number of pixels and/or tiles that include multiple triangles and are therefore painted more than once in rendering the polygon. Thus, the increased “spikiness” of a triangulation may place increased demands on the computing resources used in rendering, and performance may be degraded accordingly. For example, when a GPU is used to render the triangulated polygon, a pixel shader of the GPU may be invoked more often for areas encompassing particularly “spiky” triangles, such as the central region of the example triangulation 50.